package SwordPointOffer.DynamicProgramming;


import SwordPointOffer.Tree.Tree;
import org.junit.Test;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

 class TreeNode {
     int val;
     TreeNode left;
    TreeNode right;
     TreeNode(int x) { val = x; }
}

public class Fibonacci {

    @Test
    public void canIWin() {

        System.out.println((double) (8>>5));
    }
    public void dp(List<Integer> list, int[] dp, int desiredTotal){

    }












    @Test
    public void repeatedNTimes() {
        int[] nums = {1, 3, 4,1};
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.get(nums[i])==null) {
                map.put(nums[i], 1);
            }else{
                map.put(nums[i], map.get(nums[i])+1);
            }
        }
        Set<Integer> set = map.keySet();
        for(Integer s:set){
            if(map.get(s)==2){
                list.add(s);
            }
        }

        System.out.println(map);
    }

    public void repeatedNTimes1() {
        int a = 0;

        int[] nums = {2,6,2,1};
        Set<Integer> arr = new HashSet<>();
        for(int i=1; i<nums.length; i++){
            if(arr.add(nums[i])==false){
                System.out.println(nums[i]);
            }
        }
        System.out.println(-1);
    }

    @Test
    public void printNumbers() {
        int n = 2;
        int len =(int) Math.pow(10,n);
        int[] res = new int[len];
        for(int i=1; i<Math.pow(10,n);i++){
            res[i] = i;
        }
        String s = Arrays.toString(res);
        System.out.println(s);
    }
    @Test
    public void minNumber() {
        int[] nums = {10,2};
    }








    @Test
    public void kthLargest() {
        int k = 1;
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.left.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        List<Integer> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root!=null)queue.add(root);
        while(!queue.isEmpty()){
            for(int i=0;i<queue.size(); i++){
                root = queue.poll();
                list.add(root.val);
                if(root.right!=null)queue.add(root.right);
                if(root.left!=null)queue.add(root.left);
            }
        }
        int[] arr = new int[list.size()];
        for(int i=0;i<list.size();i++){
            arr[i] = list.get(i);
        }
        Arrays.sort(arr);
        System.out.println(arr[arr.length - 1 - k]);
    }

    @Test
    public void pathSum() {


        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.left.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        int sum = 4;
        LinkedList<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        recur(root, sum, res, path);
        System.out.println(res);
    }
    void recur(TreeNode root, int tar,
               LinkedList<List<Integer>> res, LinkedList<Integer> path) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar, res, path);
        recur(root.right, tar, res, path);
        path.removeLast();
    }







    @Test
    public void Count() {
        int m = 40;
        m = m % 10 + (Integer)(m/10);
        System.out.println(m);
    }



    @Test
    public void movingCount() {
        int m = 16,  n = 8,  k = 4;
        int sum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i<10 && j<10 && i + j <= k){
                    sum++;
                }else if (i>9 && j<10){
                    if(i%10 +  (Integer)(i/10) + j <= k ) {
                        sum++;
                    }
                }else if (j>9 && i<10){
                    if(j%10 +  (Integer)(j/10) + i <= k ) {
                        sum++;
                    }
                }else if (j>10 && i>10){
                    if(j%10 +  (Integer)(j/10) + i%10 +  (Integer)(i/10) < k ) {
                        sum++;
                    }
                }
            }
        }
        System.out.println(sum);
    }

    @Test
    public void exist(){
//        char[][] board = {
//                {'A','B','C','E'},
//                {'S','F','C','S'},
//                {'A','D','E','E'},
//                };
//        String word = "ABCCED";

            char[][] board = {
                {'A','B'},
                {'S','F'},
                };
            String word = "AB";

            //遍历找到头字母, 然后进行判定
            char[] arr = word.toCharArray();

            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if(board[i][j] == arr[0]){
                        // 递归进行判定 这个条件一加，算法复杂度提升一个量级；
                        if(judgeHead(board, arr, i, j, 0)==true){
                            System.out.println(true);
                        }
                    }
                }
            }
        System.out.println(false);
    }

    public boolean judgeHead(char[][] board, char[] word, int i, int j, int len){

        if(i>=board.length||i<0||j>=board[0].length||j<0 || word[len]!=board[i][j])return false;
        if(word.length-1 == len)return true;
        board[i][j] = '\0';
        boolean result = (judgeHead(board, word, i+1, j, len+1)||
                judgeHead(board, word, i-1, j, len+1) ||
                judgeHead(board, word, i, j+1, len+1) ||
                judgeHead(board, word, i, j-1, len+1));
        //这里要修复原来的矩阵；

        System.out.println(board);
        board[i][j] = word[len];
        System.out.println(board);
        return result;
    }








    @Test
    public void isSubStructure(){
        TreeNode A = new TreeNode(1);
        A.left = new TreeNode(2);
        A.left.right = new TreeNode(3);
        A.left.left = new TreeNode(1);
        A.right = new TreeNode(2);
        A.right.right = new TreeNode(3);
        TreeNode B = new TreeNode(2);
        B.left = new TreeNode(1);

        List<Boolean> bool = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        if(A!=null){
            queue.add(A);
        }
        while(!queue.isEmpty()){
            for (int i = queue.size(); i > 0; i--) {
                TreeNode temp = queue.poll();

                if(temp.left!=null)queue.add(temp.left);
                if(temp.right!=null)queue.add(temp.right);
                if(temp.val==B.val){
                    System.out.println(judge(temp, B));
                }
            }
        }
    }
    public Boolean judge(TreeNode temp, TreeNode B){
        if(B==null){
            return true;
        }
        if((temp==null)||(temp.val!=B.val))return false;
        return judge(temp.right,B.right)&&judge(temp.left,B.left);
    }













    @Test
    public void reverseWords(){
        String s = "  hello world!  ";
        s.trim();
        int r = s.length()-1, l = r;
        StringBuilder res = new StringBuilder();
        while(l>=0){
            while (l>=0&&s.charAt(l)!=' ')l--;
            res.append(s.substring(l+1, r+1) + " ");
            while (l>=0&&s.charAt(l)==' ')l--;
            r = l;
        }

        System.out.println(res);
    }



    public void pop(int[] nums){
        String s = Arrays.toString(nums);
        System.out.println(s);
    }

    @Test
    public void twoSum(){
        int[] nums = {45,46,67,73,74,74,77,83,89,98};

        int target = 147;
        int l=0, r=nums.length;
        int[] list = new int[2];
        int mid = (l+r)/2;
        while(l<r){
            if(nums[l]+nums[mid]==target){
                list[0] = nums[l];
                list[1] = nums[mid];
                 pop(list);
            }else if(nums[l]+nums[mid]>target){
                mid--;
            }else{
                mid++;
            }
            if(mid==l||mid==r){
                l++;
                mid = (l+r)/2;
            }
        }
        pop(nums) ;


    }

    @Test
    public void exchange(){
        int[] nums = {1,2,3,4,5};
        int l = 0, r = nums.length-1;
        while(l<r){
            if(nums[l]%2==0){
                int temp = nums[l];
                if(nums[r]%2!=0){
                    nums[l] = nums[r];
                    nums[r] = temp;
                    l++; r--;
                }else{
                    r--;
                }
            }else{
                l++;
            }
        }
        String s = Arrays.toString(nums);
        System.out.println(s);


    }




    @Test
    public void deleteNode(){
        ListNode head = new ListNode(1);
        int k = 1;
        ListNode cur = head;
        int len = 0;
        while(cur!=null){
            cur = cur.next;
            len++;
        }
        System.out.print(len);
        System.out.println(k);
        while(head!=null){
            if(len==k){
                System.out.println(head);;
            }else{
                head = head.next;
            }
            len--;
        }
        System.out.println(-1);;


    }



    @Test
    public void lengthOfLongestSubstring(){
        String s = "abcabcbb";
        int len =s.length();
        int[] dp = new int[len];
        int max = 0;
        for (int i = 0; i < len; i++) {
            int cur = 0;
            Set<String> set = new LinkedHashSet<>();
            for (int j = i; j < len; j++) {

//                if(s.substring(j,j+1).compareTo(s.substring(i,i+1))==0) {
//                    System.out.println(s.substring(j));
                if (!set.add(s.substring(j,j+1))){
                    break;
                }
                cur++;
            }
            set.clear();
            dp[i] = cur;
        }

        String a = Arrays.toString(dp);
        System.out.println(a);


    }

/**
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，
 * 1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。
 * 请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法
 *dp 思想
 *
 * */
    @Test
    public void translateNum(){
        int num = 1234256152;
        //判断长度
        String s = String.valueOf(num);
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            String temp = s.substring(i-2,i);
            if(temp.compareTo("10")>=0&&temp.compareTo("25")<=0){
                dp[i] = dp[i-2]+dp[i-1];
            }else{
                dp[i] = dp[i-1];
            }
        }
        String a = Arrays.toString(dp);
        System.out.println(a);

    }

//    String s = String.valueOf(num);
//    int[] dp = new int[s.length()+1];
//    dp[0] = 1;
//    dp[1] = 1;
//        for(int i = 2; i <= s.length(); i ++){
//        String temp = s.substring(i-2, i);
//        if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
//            dp[i] = dp[i-1] + dp[i-2];
//        else
//            dp[i] = dp[i-1];
//    }
//        return dp[s.length()];











    @Test
    public void maxSubArray(){
        int[][] grid = {
                {1,3,1},
                  {1,5,1},
                  {4,2,1}
        };

        int[][] dp = new int[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i==0&&j==0){
                    dp[0][0] = grid[0][0];
                }else if(i==0){
                    dp[i][j] = dp[i][j-1]+grid[i][j];
                }else if(j==0){
                    dp[i][j] = dp[i-1][j]+grid[i][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j]);
                }
            }
        }
        String s = Arrays.toString(dp[2]);
        System.out.println(s);

    }















    @Test
    public void fib(){
        int n = 45;
        int fib = 0;
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        for (int i = 2; i <= n; i++) {
            list.add(list.get(i-1) + list.get(i-2));
        }
        System.out.println(list);


        System.out.println( list.get(n));


    }












}
